#ifndef __DIFF_H__
#define __DIFF_H__

////////////////////////////////////////////////////////////////////////////////
// Includes
////////////////////////////////////////////////////////////////////////////////

#include <string>
#include <vector>
#include <utility>
#include <sstream>
#include "SizeException.hpp"

////////////////////////////////////////////////////////////////////////////////
// Namespaces
////////////////////////////////////////////////////////////////////////////////

namespace Toolkit  {

////////////////////////////////////////////////////////////////////////////////
// Implementation
////////////////////////////////////////////////////////////////////////////////

// Light C style interface
#define DiffStr	Diff::DiffStrings
#define DiffVec	Diff::DiffVectors

/**
 *  This class provides conversion function
 */
class Diff {
	
	public:
		
		/// Returns the changes to get from str1 to str2
		/// A change is a pair containing:
		///	  - the index of the change
		///	  - the substring to replace
		/// The two strings must be of the same size
		static std::vector< std::pair<unsigned int, std::string> > DiffStrings(
			const std::string & str1,
			const std::string & str2
		) {
			using namespace std;
			if (str1.size() != str2.size()) {
				stringstream ss;
				ss << "Strings differences: strings should be of same size. Found " << str1.size() << " and " << str2.size();
				throw Exceptions::SizeException(ss.str());
			}
			vector< pair<unsigned int, string> > result;
			string changes;
			for (unsigned int i=0; i< str1.size(); ++i) {
				if (str1[i] != str2[i]) {
					changes += str2[i];
				}
				else if (!changes.empty()) {
					result.push_back(pair<unsigned int, string>(i-changes.size(),changes));
					changes.clear();
				}
			}
			return result;
		}
		
		/// Returns the changes to get from v1 to v2
		/// A change is a pair containing:
		///	  - the nature of the change (true if gaining, false if loosing)
		///	  - the subject of the change
		template <typename T> static std::vector< std::pair<bool, T> > DiffVectors(
			const std::vector<T> & v1,
			const std::vector<T> & v2
		) {
			using namespace std;
			vector< pair<bool, T> > result;
			bool found;
			for (unsigned int i=0; i< v1.size(); ++i) {
				found = false;
				for (unsigned int j=0; (j< v2.size()) && (!found); ++j)
					if (v1[i] == v2[j]) found = true;
				if (!found) result.push_back(pair<bool, T>(false,v1[i]));
			}
			for (unsigned int i=0; i< v2.size(); ++i) {
				found = false;
				for (unsigned int j=0; (j< v1.size()) && (!found); ++j)
					if (v2[i] == v1[j]) found = true;
				if (!found) result.push_back(pair<bool, T>(true,v2[i]));
			}
			return result;
		}

};

////////////////////////////////////////////////////////////////////////////////
// Closing Namespaces
////////////////////////////////////////////////////////////////////////////////

}

////////////////////////////////////////////////////////////////////////////////

#endif

